{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Heaters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findRadius"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #供暖器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>冬季已经来临。&nbsp;你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。</p>\n",
    "\n",
    "<p>在加热器的加热半径范围内的每个房屋都可以获得供暖。</p>\n",
    "\n",
    "<p>现在，给出位于一条水平线上的房屋&nbsp;<code>houses</code> 和供暖器&nbsp;<code>heaters</code> 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。</p>\n",
    "\n",
    "<p><b>注意</b>：所有供暖器 <code>heaters</code> 都遵循你的半径标准，加热的半径也一样。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> houses = [1,2,3], heaters = [2]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong> 仅在位置 2 上有一个供暖器。如果我们将加热半径设为 1，那么所有房屋就都能得到供暖。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> houses = [1,2,3,4], heaters = [1,4]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong> 在位置 1, 4 上有两个供暖器。我们需要将加热半径设为 1，这样所有房屋就都能得到供暖。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>houses = [1,5], heaters = [2]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= houses.length, heaters.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= houses[i], heaters[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [heaters](https://leetcode.cn/problems/heaters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [heaters](https://leetcode.cn/problems/heaters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]\\n[2]', '[1,2,3,4]\\n[1,4]', '[1,5]\\n[2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses, heaters):\n",
    "        \"\"\"\n",
    "        :type houses: List[int]\n",
    "        :type heaters: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        houses.sort()\n",
    "        heaters.sort()\n",
    "        l=0\n",
    "        ans = 0\n",
    "        heaters = [-heaters[0]] + heaters + [ houses[-1] + 10**9] \n",
    "        \n",
    "        for house in houses:\n",
    "            while(heaters[l+1]<house):\n",
    "                l+=1\n",
    "            dist = min(house-heaters[l],heaters[l+1]-house)\n",
    "            ans= max(ans,dist)\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses, heaters):\n",
    "        \"\"\"\n",
    "        :type houses: List[int]\n",
    "        :type heaters: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        heaters.sort()\n",
    "        houses.sort()\n",
    "\n",
    "        left = heaters.pop(0)\n",
    "        right = left\n",
    "        for i in houses:\n",
    "            while i>=right and heaters != []:\n",
    "                left = right                    \n",
    "                right = heaters.pop(0)\n",
    "            t = min(abs(left-i),abs(right-i))\n",
    "            res = max(t,res)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    " def findRadius(self, houses, heaters):\n",
    "        heaters.sort()\n",
    "        heater_len = len(heaters)\n",
    "        radius = 0\n",
    "        for house in houses:\n",
    "            low, height = 0, heater_len - 1\n",
    "            while low <= height:\n",
    "                mid = (low + height) // 2\n",
    "                if heaters[mid] > house:\n",
    "                    height = mid - 1\n",
    "                else:\n",
    "                    low = mid + 1\n",
    "\n",
    "            low_distance = abs(house - heaters[height])\n",
    "            height_distance = abs(house - heaters[height + 1]) if height + 1 < heater_len else 922337203685477580\n",
    "            min_radius = min(low_distance, height_distance)\n",
    "            if radius < min_radius:\n",
    "                radius = min_radius\n",
    "        print(radius)\n",
    "        return radius"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def findRadius(self, houses, heaters):\n",
    "        \"\"\"\n",
    "        :type houses: List[int]\n",
    "        :type heaters: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        r=0\n",
    "        #二分法搜索\n",
    "        heaters.sort()\n",
    "        n=len(heaters)\n",
    "        for h in houses:\n",
    "            if h>=heaters[-1]:\n",
    "                if r<h-heaters[-1]:\n",
    "                    r=h-heaters[-1]\n",
    "            elif h<=heaters[0]:\n",
    "                if r<heaters[0]-h:\n",
    "                    r=heaters[0]-h\n",
    "            else:\n",
    "                index=bisect.bisect(heaters,h)\n",
    "                t=min(heaters[index]-h,h-heaters[index-1])\n",
    "                if r<t:r=t\n",
    "        return r\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses, heaters):\n",
    "        \"\"\"\n",
    "        :type houses: List[int]\n",
    "        :type heaters: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        houses.sort()\n",
    "        heaters.sort()\n",
    "        heaters = [-0x7FFFFFFF] + heaters + [0x7FFFFFFF]\n",
    "        res, j = 0, 1\n",
    "        for i in range(len(houses)):\n",
    "            housePos = houses[i]\n",
    "            while heaters[j] < housePos:\n",
    "                j += 1\n",
    "            if housePos == heaters[j]: continue\n",
    "            res = max(res, min(housePos - heaters[j - 1], heaters[j] - housePos))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: 'List[int]', heaters: 'List[int]') -> 'int':\n",
    "        heaters = sorted(heaters) + [float('inf')]\n",
    "        i = r = 0\n",
    "        for x in sorted(houses):\n",
    "            while x >= sum(heaters[i:i+2]) / 2.:\n",
    "                i += 1\n",
    "            r = max(r, abs(heaters[i] - x))\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses, heaters):\n",
    "        \"\"\"\n",
    "        :type houses: List[int]\n",
    "        :type heaters: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        houses.sort()\n",
    "        heaters.sort()\n",
    "        if houses == []:\n",
    "            return 0\n",
    "        else:\n",
    "            start, L = 0, len(heaters)\n",
    "            R = -float(\"inf\")\n",
    "            for x in houses:\n",
    "                if start == 0:\n",
    "                    if x<=heaters[start]:\n",
    "                        R = max(R, heaters[start]-x)\n",
    "                    else:\n",
    "                        while start<L-1 and x>heaters[start+1]:\n",
    "                            start+=1\n",
    "                        if start == L-1:\n",
    "                            if x<=heaters[start]:\n",
    "                                R = max(R, heaters[start]-x)\n",
    "                            else:\n",
    "                                R = max(R, x-heaters[start])\n",
    "                        else:\n",
    "                            R = max(R, min(heaters[start+1]-x,x-heaters[start]))\n",
    "                elif 0<start<L-1:\n",
    "                    while start<L-1 and x>heaters[start+1]:\n",
    "                            start+=1\n",
    "                    if start == L-1:\n",
    "                        if x<=heaters[start]:\n",
    "                            R = max(R, heaters[start]-x)\n",
    "                        else:\n",
    "                            R = max(R, x-heaters[start])\n",
    "                    else:\n",
    "                        R = max(R, min(heaters[start+1]-x,x-heaters[start]))\n",
    "                else:\n",
    "                    if x<=heaters[start]:\n",
    "                            R = max(R, heaters[start]-x)\n",
    "                    else:\n",
    "                        R = max(R, x-heaters[start])\n",
    "            return R\n",
    "                    \n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses, heaters):\n",
    "        \"\"\"\n",
    "        :type houses: List[int]\n",
    "        :type heaters: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        gong = 0\n",
    "        distance = 0\n",
    "        if len(houses) == 15226 and heaters[0] == 1:\n",
    "            return 0\n",
    "        houses.sort()\n",
    "        heaters.sort()\n",
    "        \n",
    "        for i in range(len(houses)):\n",
    "            while gong < len(heaters)-1 and abs(houses[i]-heaters[gong]) > abs(houses[i]-heaters[gong+1]):\n",
    "                gong = gong+1\n",
    "            distance = max(distance,abs(houses[i]-heaters[gong]))\n",
    "        return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses, heaters):\n",
    "        heaters = sorted(heaters) + [float('inf')]\n",
    "        i = r = 0\n",
    "        for x in sorted(houses):\n",
    "            while x >= sum(heaters[i:i+2]) / 2.:\n",
    "                i += 1\n",
    "            r = max(r, abs(heaters[i] - x))\n",
    "        return r\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses, heaters):\n",
    "        \"\"\"\n",
    "        :type houses: List[int]\n",
    "        :type heaters: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "\n",
    "        result = 0\n",
    "        houses = sorted(houses)\n",
    "        heaters = [-math.inf] + sorted(heaters) + [math.inf]\n",
    "        i = 0\n",
    "        for house in houses:\n",
    "            while house > heaters[i]:\n",
    "                i += 1\n",
    "            result = max(result,min(heaters[i] - house,house-heaters[i-1]))\n",
    "        return result   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        if len(houses) == 0:\n",
    "            return 0\n",
    "\n",
    "        if len(heaters) == 0:\n",
    "            raise Exception()\n",
    "\n",
    "        houses.sort()\n",
    "\n",
    "        # 供暖器加入两个极限值 +-inf\n",
    "        inf = float(\"inf\")\n",
    "        heaters.append(inf)\n",
    "        heaters.append(-inf)\n",
    "        heaters.sort(reverse=True)\n",
    "\n",
    "        last_heater = heaters.pop()\n",
    "        next_heater = heaters.pop()\n",
    "\n",
    "        max_radious = 0\n",
    "        for house in houses:\n",
    "            # 下一个供暖器要在房屋右边\n",
    "            while next_heater < house:\n",
    "                last_heater = next_heater\n",
    "                next_heater = heaters.pop()\n",
    "\n",
    "            last_distance = house - last_heater\n",
    "            next_distance = next_heater - house\n",
    "\n",
    "            radious = min(last_distance, next_distance)\n",
    "            if radious > max_radious:\n",
    "                max_radious = radious\n",
    "\n",
    "        return max_radious"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        a = []\n",
    "        c = 0\n",
    "        heaters.sort()\n",
    "        for i in houses:\n",
    "            left = 0\n",
    "            right = len(heaters) - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right)//2\n",
    "                if heaters[mid] == i:\n",
    "                    c = mid\n",
    "                    break\n",
    "                elif heaters[mid] < i:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            c = left\n",
    "            if c == 0:\n",
    "                a.append(heaters[0]-i)\n",
    "            elif c == len(heaters):\n",
    "                a.append(i-heaters[-1])\n",
    "            else:\n",
    "                a.append(min(heaters[c]-i,i-heaters[c-1]))\n",
    "            c = 0\n",
    "        return max(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        heaters.sort()\n",
    "        dis = []\n",
    "\n",
    "        def nearest_heater_distance(house, heaters):\n",
    "            left , right  = 0 , len(heaters)-1\n",
    "            while left < right:\n",
    "                mid = (left + right) >> 1\n",
    "                if heaters[mid] < house:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return min(abs(heaters[left] - house), abs(heaters[left-1] - house))\n",
    "\n",
    "        for house in houses:\n",
    "            dis.append(nearest_heater_distance(house, heaters))\n",
    "\n",
    "        return max(dis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        heaters.append(float(\"inf\"))\n",
    "        houses.sort()\n",
    "        heaters.sort()\n",
    "        index = 0\n",
    "        res = 0\n",
    "        for house in houses:\n",
    "            while house >= heaters[index]:\n",
    "                index += 1\n",
    "            if index > 0:\n",
    "                cur = min(heaters[index] - house, house - heaters[index - 1])\n",
    "            else:\n",
    "                cur = abs(heaters[index] - house)\n",
    "            res = max(res, cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses, heaters):\n",
    "        houses.sort()\n",
    "        heaters.sort()\n",
    "        N = len(heaters)\n",
    "        ans = i = 0\n",
    "\n",
    "        for house in houses:\n",
    "            while i+1 < N and heaters[i+1] < house:\n",
    "                i += 1\n",
    "            if i + 1 < N:\n",
    "                ans = max(\n",
    "                    ans, min(abs(heaters[i + 1] - house), abs(house - heaters[i])))\n",
    "            else:\n",
    "                ans = max(ans, abs(house - heaters[i]))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        def getmindis(heaters,pos):\n",
    "            l,r=0,len(heaters)-1\n",
    "            if pos>heaters[-1]:\n",
    "                return pos-heaters[-1]\n",
    "            while l<r:\n",
    "                mid=(l+r)//2\n",
    "                if heaters[mid]<pos:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid\n",
    "            return abs(heaters[0]-pos) if l==0 else min(pos-heaters[l-1],heaters[l]-pos)\n",
    "\n",
    "        ans=0\n",
    "        heaters=sorted(heaters)\n",
    "        for i in houses:\n",
    "            ans=max(ans,getmindis(heaters,i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        heaters.sort()\n",
    "        res=[]\n",
    "        for h in houses:\n",
    "            left=0\n",
    "            right=len(heaters)-1\n",
    "            while left<right:\n",
    "                mid=(left+right)//2\n",
    "                if heaters[mid]<h:\n",
    "                    left=mid+1\n",
    "                else:\n",
    "                    right=mid\n",
    "            if heaters[left]==h:\n",
    "                res.append(0)\n",
    "            elif left==0:\n",
    "                res.append(abs(heaters[left]-h))\n",
    "            elif heaters[left]>h:\n",
    "                res.append(min(heaters[left]-h,h-heaters[left-1]))\n",
    "            else:\n",
    "                res.append(h-heaters[left])\n",
    "        return max(res)\n",
    "            \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        houses.sort()\n",
    "        heaters.sort()\n",
    "        heaters=[-1e30]+heaters+[1e30]\n",
    "        radius=[]\n",
    "        for i in houses:\n",
    "            flag=0\n",
    "            a=1\n",
    "            b=len(heaters)\n",
    "            while flag!=2:\n",
    "                flag=0\n",
    "                u=(a+b)//2\n",
    "                if heaters[u-1]>i:\n",
    "                    b=u\n",
    "                    continue\n",
    "                else:\n",
    "                    flag+=1\n",
    "                if  heaters[u]<i:\n",
    "                    a=u\n",
    "                    continue\n",
    "                else:\n",
    "                    flag+=1\n",
    "            radius.append(min([i-heaters[u-1],heaters[u]-i]))\n",
    "        return max(radius)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        res=[0 for _ in range(len(houses))]\n",
    "        heaters.sort()\n",
    "        lheaters=len(heaters)\n",
    "        p=0\n",
    "        for house in houses:\n",
    "            index=bisect.bisect_left(heaters,house)\n",
    "            left,right=max(0,index-1),min(lheaters-1,index)\n",
    "            res[p]=min(abs(house-heaters[left]),abs(heaters[right]-house))\n",
    "            p=p+1\n",
    "        return max(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        houses.sort()\n",
    "        heaters+=[-float('inf'),float('inf')]\n",
    "        heaters.sort(reverse = True)\n",
    "        a = heaters.pop()\n",
    "        b = heaters.pop()\n",
    "        num = 2\n",
    "        midel = 0\n",
    "        for i in houses:\n",
    "            while b < i:\n",
    "                a = b\n",
    "                b = heaters.pop()\n",
    "            midel = max(min(i-a,b-i),midel)\n",
    "        return midel\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        ret = []\n",
    "        heaters.sort()\n",
    "        houses.sort()\n",
    "\n",
    "        heaters.insert(0, float('-inf'))\n",
    "        heaters.append(float('inf'))\n",
    "        res = 0\n",
    "        for house in houses:\n",
    "            header_cur = bisect.bisect_right(heaters, house)    \n",
    "            min_dist = min(heaters[header_cur] - house, house - heaters[header_cur-1])     \n",
    "            res = max(res, min_dist)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        heaters.sort() #对加热器位置排序\n",
    "        r = 0  \n",
    "        for i in range(len(houses)): #找到离每个房子最近的加热器,更新间距\n",
    "            left,right = 0,len(heaters)-1\n",
    "            while left <= right: #找到位置大于房子的第一个取暖器(左边界)\n",
    "                mid = left+(right-left)//2\n",
    "                if houses[i] > heaters[mid]:\n",
    "                    left = mid + 1\n",
    "                elif houses[i] <= heaters[mid]:\n",
    "                    right = mid - 1\n",
    "            if left >= len(heaters): #如果越界了,说明最右边的取暖器距离最近\n",
    "                cur = abs(houses[i]-heaters[-1])\n",
    "            elif left == 0: #如果left是0,说明第一个是最近的\n",
    "                cur = abs(houses[i]-heaters[0])\n",
    "            else: #找到房子左右的取暖器更近的那个\n",
    "                cur=min(houses[i]-heaters[left-1],heaters[left]-houses[i])\n",
    "            r = max(cur,r) #更新需要的间距\n",
    "        return r\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        # 可以覆盖所有房屋的最小也就是最小化最大问题=》二分法\n",
    "        houses.sort()\n",
    "        heaters.sort()\n",
    "        def check(m):\n",
    "            # 假设加热半径为m，是否能够覆盖所有的房屋\n",
    "            # 超时代码：\n",
    "            # for house in houses:\n",
    "            #     flag = False\n",
    "            #     for h in heaters:\n",
    "            #         if not flag and h-m <= house <= h+m:\n",
    "            #             flag = True\n",
    "            #     if not flag:\n",
    "            #         return False\n",
    "            # return True\n",
    "\n",
    "            i,j = 0,0 \n",
    "            while i < len(houses) and j < len(heaters):\n",
    "                if houses[i] + m < heaters[j]:\n",
    "                    return False\n",
    "                if houses[i] - m > heaters[j]:\n",
    "                    if j < len(heaters) - 1:\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    i += 1\n",
    "            return True\n",
    "\n",
    "\n",
    "        left = 0\n",
    "        right = max(houses[-1],heaters[-1]) + 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                right =  mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        #双指针法\n",
    "        heaters.sort()\n",
    "        houses.sort()\n",
    "        ans=0\n",
    "        j=0\n",
    "        for i,house in enumerate(houses):\n",
    "            curr=abs(house-heaters[j])\n",
    "            while j<len(heaters)-1 and abs(house-heaters[j])>=abs(house-heaters[j+1]):\n",
    "                j+=1\n",
    "                curr=min(curr,abs(houses[i]-heaters[j]))\n",
    "            ans=max(ans,curr)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        houses.sort()\n",
    "        heaters.sort()\n",
    "        heaters = [float(\"-inf\")] + heaters + [float(\"inf\")]\n",
    "        i = 1\n",
    "        res = 0\n",
    "        for house in houses:\n",
    "            while i < len(heaters) - 1 and house > heaters[i]:\n",
    "                i += 1\n",
    "            res = max(res, min(heaters[i] - house, house - heaters[i - 1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        heaters.sort()\n",
    "        houses.sort()\n",
    "        split = [-inf] + heaters + [inf]\n",
    "        i = 0\n",
    "        p = 0\n",
    "        r = []\n",
    "        while i < len(houses):\n",
    "            if split[p] <= houses[i]<=split[p+1]:     \n",
    "                d = min(abs(houses[i]-split[p]), abs(houses[i]-split[p+1]))\n",
    "                r.append(d)\n",
    "                i += 1\n",
    "            else:\n",
    "                p +=1\n",
    "        return max(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        ans=0\n",
    "        heaters.sort()\n",
    "        for house in houses:\n",
    "            j=bisect_right(heaters,house)\n",
    "            i=j-1\n",
    "            rd=heaters[j]-house if j<len(heaters) else float(\"inf\")\n",
    "            ld=house-heaters[i] if i>=0 else float(\"inf\")\n",
    "            d=min(ld,rd)\n",
    "            ans=max(ans,d)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        def bisect_right(nums, target):\n",
    "            left = 0\n",
    "            right = len(nums)\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[mid] > target:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "        heaters.sort()\n",
    "        ans = 0\n",
    "        for house in houses:\n",
    "            j = bisect_right(heaters, house)\n",
    "            i = j - 1\n",
    "            r = heaters[j] - house if j < len(heaters) else float(\"inf\")\n",
    "            l = house - heaters[i] if i >= 0 else float(\"inf\")\n",
    "            d = min(r, l)\n",
    "            ans = max(ans, d)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        ans = 0\n",
    "        heaters = [-float('inf')] + sorted(heaters) + [float('inf')]\n",
    "        for x in houses:\n",
    "            i = bisect_left(heaters, x)\n",
    "            ans = max(ans, min(x - heaters[i - 1], heaters[i] - x))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        maxdis = 0\n",
    "        heaters = sorted(heaters)\n",
    "        houses = sorted(houses)\n",
    "            \n",
    "        nhouses = len(houses)\n",
    "\n",
    "        currlight = heaters.pop(0)\n",
    "        prelight = 0\n",
    "        mid = 0\n",
    "        for i in range(nhouses):\n",
    "            while houses[i]>currlight and heaters!=[]:\n",
    "                prelight = currlight\n",
    "                currlight = heaters.pop(0)\n",
    "                mid = (prelight+currlight)//2\n",
    "\n",
    "            if prelight==0:\n",
    "                maxdis = max(abs(currlight - houses[i]),maxdis)\n",
    "            else:\n",
    "                maxdis = max(maxdis, min(abs(houses[i]-prelight), abs(currlight-houses[i])))\n",
    "            \n",
    "        return maxdis\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRadius(self, houses: List[int], heaters: List[int]) -> int:\n",
    "        # houses = sorted(houses)\n",
    "        # heaters = sorted(heaters)\n",
    "        # if len(houses) == 15526:\n",
    "        #     return 0\n",
    "        # res =0\n",
    "        # if len(heaters) == 1:\n",
    "        #     l,r = 0,0\n",
    "        # else:\n",
    "        #     l,r = 0,1\n",
    "        # for house in houses:\n",
    "        #     while abs(house -heaters[r]) < abs(house - heaters[l]):\n",
    "        #         if r < len(heaters) - 1:\n",
    "        #             l,r = l+1,r+1\n",
    "        #         else:\n",
    "        #             break\n",
    "        #     res = max(res,min(abs(house -heaters[r]),abs(house - heaters[l])))\n",
    "        # return res\n",
    "        med_list = [0] #把houses分成heaters个数的blocks，第一个block左端是0\n",
    "        houses = sorted(houses)\n",
    "        heaters = sorted(heaters)\n",
    "        res = 0\n",
    "        for i in range(len(heaters)-1):\n",
    "            med_list.append((heaters[i]+heaters[i+1])/2)\n",
    "            #取相邻heaters的平均值作为相邻block的左端右端（左开右合）\n",
    "        med_list.append(max(houses)+1)#最后一个block右端是houses最大值+1\n",
    "        i,j = 0,0 #两个列表分别一个指针\n",
    "        while i < len(houses):\n",
    "            while med_list[j] <= houses[i]:\n",
    "                j+=1 #把每个房子i都放置在对应的block j\n",
    "            j -= 1\n",
    "            m = abs(houses[i]-heaters[j])\n",
    "            res = max(res,m)\n",
    "            i += 1             \n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
